package 图;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
/**
 * 这道题 最棘手的 一个问题 就是  突变的 顺序    无法 确定
 * 刚开始 以为 简单的 从左 到右 进行 突变  即可 但是 这样  是错的  因为 这样 突变 可能 不在 bank 里面
 * 而 按照 中间的 乱序 突变 可能  success  主要 是这个点  
 *  
 * 所以需要 枚举 所有的 一个 过程？？ 
 */
/**
 * bfs 的 相关题目 直接 归为 图 
 * 这道题 其实本身 就是可以  用图的 方式来解决
 *最初的   疑惑 就是 因为 这个  题意 并没有 理解 清楚 
 *这他妈 这个题  本身 的 题意  就很扯淡  
 *其实  细细的 去思考 发现 这道题 并不是 很容易
 * 可以尝试   用图的方式    去解决  顺便 复习 一下 链式前向星的  存图方式
 * 
 * 最后 在  尝试一下 dfs 的方式 
 */
public class leetcode433最小基因变化 {
		public static void main(String []args) {
			int arr [] = {1,2,3,4};
			int[] arr1 = arr.clone();
			System.out.println(Arrays.toString(arr1));
			System.out.println(arr + "    " + arr1);
		}
}
class Solu {
    static char[] items = new char[]{'A', 'C', 'G', 'T'};
    public int minMutation(String S, String T, String[] bank) {
        Set<String> set = new HashSet<>();
        for (String s : bank) set.add(s);
        Deque<String> d = new ArrayDeque<>();
        Map<String, Integer> map = new HashMap<>();
        d.addLast(S);
        map.put(S, 0);
        while (!d.isEmpty()) {
            int size = d.size();
            while (size-- > 0) {
//            	int a = 10;
                String s = d.pollFirst();
                char[] cs = s.toCharArray();
                int step = map.get(s);
                for (int i = 0; i < 8; i++) {
//                	if()
                    for (char c : items) {
                        if (cs[i] == c) continue;
                        char[] clone = cs.clone();
                        clone[i] = c;
                        String sub = String.valueOf(clone);
                        if (!set.contains(sub)) continue;
                        if (map.containsKey(sub)) continue;
                        if (sub.equals(T)) return step + 1;
                        map.put(sub, step + 1);
                        d.addLast(sub);
                    }
                }
            }
        }
        return -1;
    }
}
class Soluti {
    int ans = Integer.MAX_VALUE;

    public int minMutation(String start, String end, String[] bank) {
        backtrack(start, end, bank, new boolean[bank.length], 0);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public void backtrack(String start, String end, String[] bank, boolean[] used, int t) {
        if (t >= ans) return;
        if (start.equals(end)) {
            ans = Math.min(ans, t);
        } else {
            for (int i = 0, diff = 0; i < bank.length; i++, diff = 0) {
                if (used[i]) continue;
                for (int j = 0; j < start.length(); j++) 
                    diff += start.charAt(j) != bank[i].charAt(j) ? 1 : 0;
                if (diff == 1) {
                    used[i] = true;
                    backtrack(bank[i], end, bank, used, t + 1);
                    used[i] = false;
                }
            }
        }
    }
}


